﻿#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
//DP数组,因为钱最多为6000，故只开6001
int DP[6001];
//钱和可购买物品种类
int numObjects, money;
//物品价格
int weight[501];
//物品价值
int value[501];
//物品数量
int numberOfObject[501];
//多重背包优化为01背包
int divideObject[4][2]; // ⌈log2(10)⌉ = 4
int main() {
	int numberOfFormer = 0;//计件的变量
	scanf("%d%d", &numObjects, &money);
	for (int i = 1; i <= numObjects; i++) {//输入
		scanf("%d%d%d", &weight[i], &value[i], &numberOfObject[i]);
	}
	for (int i = 1; i <= numObjects; i++) {//循环
		if (numberOfObject[i] > 1) {//如果物体数量大于1，则对该种物品进行01背包优化
			int buffer = numberOfObject[i];//buffer保存第i件物品的数量
			int divideObjects = 0;//第i件物品如果优化，被分割成单个物品的总数
			while (1) {
				buffer /= 2;
				if (!buffer) {
					break;
				}
				divideObject[++divideObjects/*分割的物品个数增加*/][0] = pow(2, divideObjects - 1) * weight[i];//分隔物品的价格
				divideObject[divideObjects][1] = pow(2, divideObjects - 1) * value[i];//分割物品的价值
				numberOfFormer += pow(2, divideObjects - 1);//累计分割第i件物品的个数

			}
			if ((numberOfObject[i] - numberOfFormer)) {//如果割完了2^n后，还有剩余物品
				divideObject[++divideObjects][0] = (numberOfObject[i] - numberOfFormer) * weight[i];//则全部划分为下一个单物品
				divideObject[divideObjects][1] = (numberOfObject[i] - numberOfFormer) * value[i];
			}
			numberOfFormer = 0;//清空计件变量
			for(int j = 1; j <= divideObjects; j++)
			printf("[第%d件分割%d]价格%d价值%d\n",i,j,divideObject[j][0], divideObject[j][1]);
			for (int k = 1; k <= divideObjects; k++) {
				for (int j = money; j >= divideObject[k][0]; j--) {//divideObject[k][0]是分割的第k个物品的价格,divideObject[k][1]是价值
					DP[j] = max(DP[j], DP[j - divideObject[k][0]] + divideObject[k][1]);
				}
			}
		}
		else if (numberOfObject[i] == 0) {
			break;
		}
		else {//同理，如果第i件物品的数量是1则常规01背包
			for (int j = money; j >= weight[i]; j--) {
				DP[j] = max(DP[j], DP[j - weight[i]] + value[i]);
			}
		}
		printf("\n\n");
	}
	printf("%d", DP[money]);
	return 0;
}
